51
class Solution {
    char[][] arr;1 代表皇后
    ListListString list = new ArrayList();

    public ListListString solveNQueens(int n) {
        arr = new char[n][n];
        for (int x = 0; x  n; x++) {
            for (int y = 0; y  n; y++) {
                arr[x][y] = '.';
            }
        }
        fun(n, 0, 0, 0);
        return list;
    }

    public void fun(int n, int num, int x, int y) {
        if (num == n) {
            ListString tmp = new ArrayList();
            for (int i = 0; i  n; i++) {
                StringBuilder sb = new StringBuilder();
                for (int j = 0; j  n; j++) {
                    sb.append(arr[i][j]);
                }
                tmp.add(sb.toString());
            }
            list.add(tmp);
            return;
        }
        for (; x  n; x++) {
            for (; y  n; y++) {
                arr[x][y] = 'Q';
                if (check(x,y,n)) {
                    fun(n, num+1, x, y+1);
                }
                arr[x][y] = '.';
            }
            y = 0;
        }
    }

    public boolean check(int x, int y, int n) {
        检测横
        int sum = 0;
        for (int i = 0; i  n; i++){
            sum += arr[x][i] == 'Q'  1  0;
        }
        if (sum  1) {
            return false;
        }
        检测列
        sum = 0;
        for (int i = 0; i  n; i++) {
            sum += arr[i][y] == 'Q'  1  0;
        }
        if (sum  1) {
            return false;
        }
        检测斜边
        sum = 0;
        for (int i = x, j = y; i  n && j  n; i++, j++) {
                sum += arr[i][j] == 'Q'  1  0;
        }
        for (int i = x-1, j = y-1; i = 0 &&  j = 0; i--, j--) {
                sum += arr[i][j] == 'Q'  1  0;
        }
        for (int i = x+1, j = y-1; i  n && j = 0; i++, j--) {
                sum += arr[i][j] == 'Q'  1  0;
        }
        for (int i = x-1, j = y+1; i= 0 && j  n; i--, j++) {
                sum += arr[i][j] == 'Q'  1  0;
        }
        if (sum  1) {
            return false;
        }
        return true;
    }
}
class Solution {
    public int minStickers(String[] stickers, String target) {

        int n = stickers.length;
        int[][] sti = new int[n][26];
        for (int i = 0; i < stickers.length; i++){
            for (int j = 0; j < stickers[i].length(); j++){
                sti[i][stickers[i].charAt(j) - 'a']++;
            }
        }
        int ret = Stickers(sti, target);
        return  ret == Integer.MAX_VALUE ? -1 : ret;
    }

    public int Stickers(int[][] sti, String target){

        if (target.length() == 0){
            return 0;
        }
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < sti.length; i++){
            if (sti[i][target.charAt(0) - 'a'] > 0){
                //删除
                String tar = delChar(sti[i], target);
                int n = Stickers(sti, tar);
                min = min < n ? min : n;
            }
        }

        return min + (min == Integer.MAX_VALUE ? 0 : 1);
    }

    public String delChar(int[] sti, String target){
        int[] tar = new int[26];
        for (int i = 0; i < target.length(); i++){
            tar[target.charAt(i) - 'a']++;
        }
        String str = "";
        for (int i = 0; i < 26; i++){
            tar[i] -= sti[i];
            if (tar[i] > 0){
                while(tar[i]-- > 0){
                    str += (char)('a' + i);
                }
            }
        }
        
        return str;
    }
}